#pragma once

#include <functional>
#include <memory>
#include <vector>

/**
 * 合并算法，将两个数组进行合并
 * @param1 pElems 指向结果集的数组指针
 * @param2 nLeft 相对应Left的索引
 * @param3 nMid 相对应Mid的索引
 * @param4 nRight 相应对Right的索引
 * 
 * 需要注意的是：
 *      nLeft(包含) ~ nMid(包含)
 *      nMid + 1(包含) ~ nRight(包含nRight)
 */
template<typename T, typename compare = std::less<T>>
void Merge(T* pElems, size_t nLeft, size_t nMid, size_t nRight){
    if(pElems == nullptr)
        return;

    if(nLeft > nMid || nMid >= nRight)
        return;

    size_t nLeftLen = nMid - nLeft + 1; // 获得左边元素个数，包含pElems[nMid]
    size_t nRightLen = nRight - nMid; //

    std::vector<T> pLeftElems(nLeftLen + 1); // +1防止触发集合内存的再次分配
    std::vector<T> pRightElems(nRightLen + 1);

    //init lArray
    for(int i = 0; i < nLeftLen; ++i){
        pLeftElems[i] = pElems[nLeft + i];
    }

    //init rArray
    for(int i = 0; i < nRightLen; ++i){
        pRightElems[i] = pElems[nMid + i + 1];
    }
    int i = 0;
    int j = 0;
    compare comp;
    

    /**
     * 因为外部传入的参数均是相对应的数组索引(从0开始)而不是长度位置(从1开始).
     * 所以这里的nRight也是需要填入元素的.
     */
    for(int k = nLeft; k <= nRight; ++k){

        if(i < nLeftLen && comp(pLeftElems[i], pRightElems[j]) || j >= nRightLen)
            pElems[k] = pLeftElems[i++];
        else{
            pElems[k] = pRightElems[j++];
        }
    }
}


template<typename T, typename compare = std::less<T>>
void MergeSort(T* pElems, size_t nLeft, size_t nRight){
    if(pElems == nullptr)
        return;
        
    if(nLeft < nRight){

        size_t nMid = (nLeft + nRight) / 2;
        MergeSort(pElems, nLeft, nMid);
        MergeSort(pElems, nMid + 1, nRight);
        
        Merge<T, compare>(pElems, nLeft, nMid, nRight);
    }
}